package bird.tree.binary_search_tree;

/**
 * @author sijunqiang
 * @data 2021/6/23 22:18
 * @description: 二分搜索树
 * 注意:
 * 使用二分搜索树存储元素 元素需要具有可比较性
 */
public class BSF<E extends Comparable<E>> {

    // size 记录二分搜索树中实际存储的元素的个数
    private int size;

    // root -代表二分搜索树的根节点
    private Node root;

    // node 代表二叉树的节点 里面包含 实际存储的元素 指向左右两个孩子的节点。
    private class Node {
        public E e;// 实际存储的元素
        public Node left, right;// 指向左右两个孩子

        // 构造函数
        public Node(E e) {
            this.e = e;
            this.left = null;
            this.right = null;
        }


    }


    // 获取树中实际存储的元素个数
    public int size() {
        return size;
    }

    // 判断该该为空
    public boolean isEmpty() {
        return size == 0;
    }

// 原始的操作
//    // 往二分搜索树中添加元素
//    public void add(E e) {
//        if (root == null) {
//            root = new Node(e);
//            return;
//        }
//        add(root, e);
//    }
//
//
//     * 实现功能：向以node为根节点的二分搜索树中 插入元素e
//     * 第一步：先判断插入的元素和根节点的元素是否相同 如果相同的话 那么就停止。
//     * 第二步：如果插入的元素比根节点的元素小的话 且根节点的左孩子为null的话 那么就往这个根节点左孩子插入元素。
//     * 第三步：如果插入的元素比根节点的元素大的话 且根节点的右孩子为null的话 那么就往这个根节点右孩子插入元素。
//     * 第四步：如果插入的元素比根节点小的话 那么就往这个根节点的左子树的二分搜索树中继续比较插入元素。 --递归
//     * 第五步：如果插入的元素比根节点大的话 那么就往这个根节点的右子树的二分搜索树中继续比较插入元素。--递归
//
//    private void add(Node node, E e) {
//        if (node.e.equals(e)) {
//            return;
//        } else if (e.compareTo(node.e) < 0 && node.left == null) {
//            node.left = new Node(e);
//            size++;
//            return;
//        } else if (e.compareTo(node.e) > 0 && node.right == null) {
//            node.right = new Node(e);
//            size++;
//            return;
//        }
//        if (e.compareTo(node.e) < 0) {
//            add(node.left, e);
//        } else {
//            add(root.right, e);
//        }
//    }


    // 往二分搜索树中添加元素
    public void add(E e) {
        add(root, e);
    }


    /*
     *实现功能：向以node为根节点的二分搜索树中 插入元素e,返回插入新的节点后的根节点。 --递归操作
     *
     * 核心的思想是 只衔接节点
     * 第一步：如果二分搜索树的节点为null的话 那么添加的元素就是就是该二分搜索树的根节点。
     * 第二步：如果添加的元素比根节点小的话 那么就往左子树的方向递归的方式进行添加元素 使用当前的根节点的左孩子进行接收。
     * 第三步：如果添加的元素比根节点大的话 那么就往右子树的方向递归的方式进行添加元素 使用当前的根节点的右孩子进行接收。
     * 第四步：如果添加的元素和根节点相同的话 那么这里暂持不做处理。
     * 第五步：返回根节点。
     */
    private Node add(Node node, E e) {

        if (node == null) {
            return new Node(e);
        }

        if (e.compareTo(node.e) < 0) {
            node.left = add(node.left, e);// 这里设计的很巧妙-需要debug
        } else if (e.compareTo(node.e) > 0) {
            node.right = add(node.right, e);
        }
        return node;
    }

}

